package problem526;
//526.优美的排列
//https://leetcode.cn/problems/beautiful-arrangement/

class Solution {
    int count = 0, n = 0;
    boolean[] st;
    public int countArrangement(int _n) {
        st = new boolean[_n+1];
        n = _n;
        dfs(1);
        return count;   
    }
    
    public void dfs(int u) {
        if(u == n+1) {
            count++;
            return;
        }

        for(int i = 1; i<=n; i++) {
            if(!st[i]) {
                if(u % i == 0 || i % u == 0) {
                    st[i] = true;
                    dfs(u+1);
                    st[i] = false;
                }
            }
        }
    }
}